/**
 * @author ghp
 * @title
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        // 构建leftProduct
//        int[] leftProduct = new int[len];
//        leftProduct[0] = 1;
//        for (int i = 1; i < len; i++) {
//            leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
//        }
        // 构建rightProduct
        int[] rightProduct = new int[len];
        rightProduct[len - 1] = 1;
        for (int i = len - 2; i >= 0; i--) {
            rightProduct[i] = nums[i + 1] * rightProduct[i + 1];
        }
        int leftProduct = nums[0];
        nums[0] = rightProduct[0];
        // 计算每一个元素的左右乘积
        for (int i = 1; i < len; i++) {
            int pre = nums[i];
            nums[i] = leftProduct * rightProduct[i];
            leftProduct *= pre;
        }
        return nums;
    }
}

